package 双周赛;

import util.ListNode;

import java.util.*;

/**
 *
 */
public class 第110场双周赛 {

    public static void main(String[] args) {

        System.out.println(minimumSeconds(Arrays.asList(2, 1, 3, 3, 2)));

    }

    /**
     * 模拟+辗转相除法
     */
    public ListNode insertGreatestCommonDivisors(ListNode head) {
        ListNode curNode = head;

        while (curNode != null && curNode.next != null) {

            ListNode next = curNode.next;
            curNode.next = new ListNode(gcd(curNode.val, next.val));
            curNode = curNode.next;
            curNode.next = next;

            curNode = next;
        }

        return head;
    }

    private int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }

    /**
     * 1，如果最终的数字确定了，那么最少秒数，等于(两个最终数字最长间隔 + 1) / 2
     * 2，可以用哈希表分组，key 为最终数字，value 为 key 出现的索引列表
     */
    public static int minimumSeconds(List<Integer> nums) {
        int n = nums.size();
        int ans = Integer.MAX_VALUE;
        Map<Integer, List<Integer>> map = new HashMap<>();
        for (int i = 0; i < n; i++) {
            Integer num = nums.get(i);
            List<Integer> list = map.get(num);
            if (list == null) {
                list = new ArrayList<>();
                map.put(num, list);
            }
            list.add(i);
        }

        for (Map.Entry<Integer, List<Integer>> entry : map.entrySet()) {
            ans = Math.min(ans, (getMaxDistance(entry.getValue(), n) + 1) / 2);
        }

        return ans;
    }

    private static int getMaxDistance(List<Integer> list, int n) {
        // 环形数组，小技巧，将第一个出现的数字索引，拼接到最后一个索引后面
        list.add(list.get(0) + n);
        int maxDis = 0;
        for (int i = 1; i < list.size(); i++) {
            maxDis = Math.max(maxDis, list.get(i) - list.get(i - 1) - 1);
        }
        return maxDis;
    }

}
